{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #The Earliest and Latest Rounds Where Players Compete"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #memoization #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #记忆化搜索 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: earliestAndLatest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最佳运动员的比拼回合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><code>n</code> 名运动员参与一场锦标赛，所有运动员站成一排，并根据 <strong>最开始的</strong> 站位从 <code>1</code> 到 <code>n</code> 编号（运动员 <code>1</code> 是这一排中的第一个运动员，运动员 <code>2</code> 是第二个运动员，依此类推）。</p>\n",
    "\n",
    "<p>锦标赛由多个回合组成（从回合 <code>1</code> 开始）。每一回合中，这一排从前往后数的第 <code>i</code> 名运动员需要与从后往前数的第 <code>i</code> 名运动员比拼，获胜者将会进入下一回合。如果当前回合中运动员数目为奇数，那么中间那位运动员将轮空晋级下一回合。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，当前回合中，运动员 <code>1, 2, 4, 6, 7</code> 站成一排\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li>运动员 <code>1</code> 需要和运动员 <code>7</code> 比拼</li>\n",
    "\t\t<li>运动员 <code>2</code> 需要和运动员 <code>6</code> 比拼</li>\n",
    "\t\t<li>运动员 <code>4</code> 轮空晋级下一回合</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>每回合结束后，获胜者将会基于最开始分配给他们的原始顺序（升序）重新排成一排。</p>\n",
    "\n",
    "<p>编号为 <code>firstPlayer</code> 和 <code>secondPlayer</code> 的运动员是本场锦标赛中的最佳运动员。在他们开始比拼之前，完全可以战胜任何其他运动员。而任意两个其他运动员进行比拼时，其中任意一个都有获胜的可能，因此你可以 <strong>裁定</strong> 谁是这一回合的获胜者。</p>\n",
    "\n",
    "<p>给你三个整数 <code>n</code>、<code>firstPlayer</code> 和 <code>secondPlayer</code> 。返回一个由两个值组成的整数数组，分别表示两位最佳运动员在本场锦标赛中比拼的 <strong>最早</strong> 回合数和 <strong>最晚</strong> 回合数。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 11, firstPlayer = 2, secondPlayer = 4\n",
    "<strong>输出：</strong>[3,4]\n",
    "<strong>解释：</strong>\n",
    "一种能够产生最早回合数的情景是：\n",
    "回合 1：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\n",
    "回合 2：2, 3, 4, 5, 6, 11\n",
    "回合 3：2, 3, 4\n",
    "一种能够产生最晚回合数的情景是：\n",
    "回合 1：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\n",
    "回合 2：1, 2, 3, 4, 5, 6\n",
    "回合 3：1, 2, 4\n",
    "回合 4：2, 4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 5, firstPlayer = 1, secondPlayer = 5\n",
    "<strong>输出：</strong>[1,1]\n",
    "<strong>解释：</strong>两名最佳运动员 1 和 5 将会在回合 1 进行比拼。\n",
    "不存在使他们在其他回合进行比拼的可能。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 28</code></li>\n",
    "\t<li><code>1 &lt;= firstPlayer &lt; secondPlayer &lt;= n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [the-earliest-and-latest-rounds-where-players-compete](https://leetcode.cn/problems/the-earliest-and-latest-rounds-where-players-compete/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [the-earliest-and-latest-rounds-where-players-compete](https://leetcode.cn/problems/the-earliest-and-latest-rounds-where-players-compete/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['11\\n2\\n4', '5\\n1\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:\n",
    "        H=set()\n",
    "        def helper(l, f, s, t, idf, ifs):\n",
    "            if (len(l), idf, ifs) in H:\n",
    "                return\n",
    "            H.add((len(l), idf, ifs))\n",
    "            # print(l,t)\n",
    "            for i in range(len(l)//2):\n",
    "                if (l[i]==f and l[len(l)-1-i]==s) or (l[i]==s and l[len(l)-1-i]==f):\n",
    "                    times.add(t)\n",
    "                    return\n",
    "            for i in range(1<<(len(l)//2)):\n",
    "                # print(i,t)\n",
    "                nl=[]\n",
    "                if len(l)%2==1: nl.append(l[len(l)//2])\n",
    "                # 11111\n",
    "                for _ in range(len(l)//2):\n",
    "                    if l[_]==f or l[len(l)-1-_]==f:\n",
    "                        nl.append(f)\n",
    "                        continue\n",
    "                    if l[_]==s or l[len(l)-1-_]==s:\n",
    "                        nl.append(s)\n",
    "                        continue\n",
    "                    result=(i&(1<<(len(l)//2-1-_)))//(1<<(len(l)//2-1-_))\n",
    "                    if result==1:\n",
    "                        nl.append(l[_])\n",
    "                    else:\n",
    "                        nl.append(l[len(l)-1-_])\n",
    "                nl.sort()\n",
    "                helper(nl, f, s, t+1, nl.index(f), nl.index(s))\n",
    "            return\n",
    "        times=set()\n",
    "        l=range(1,n+1)\n",
    "        helper(l, firstPlayer, secondPlayer, 1, l.index(firstPlayer), l.index(secondPlayer))\n",
    "        return [min(times), max(times)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:\n",
    "        a, b, c = firstPlayer - 1, secondPlayer - firstPlayer - 1, n - secondPlayer\n",
    "        if a == c: return [1,1]\n",
    "        if a > c: a, c = c, a\n",
    "        ans, has = min(len(bin(n-1))-2, c+1), {}\n",
    "        def dfs(x,y,z):\n",
    "            if (x,y,z) not in has:\n",
    "                if x == z: return 1\n",
    "                if x > z: x, z = z, x\n",
    "                if z >= x + y + 2: tep = min(dfs(i,j,(x+y+z-1)//2-i-j) for i in range(x+1) for j in range(y+1))\n",
    "                else: tep = min(dfs(i,j+(x+y-z+1)//2,z-i-j-1) for i in range(x+1) for j in range(z-x))\n",
    "                has[(x,y,z)] = tep + 1\n",
    "            return has[(x,y,z)]\n",
    "        return [dfs(a,b,c), ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:\n",
    "        H=set()\n",
    "        def helper(l, f, s, t, idf, ifs):\n",
    "            if (len(l), idf, ifs) in H:\n",
    "                return\n",
    "            H.add((len(l), idf, ifs))\n",
    "            # print(l,t)\n",
    "            for i in range(len(l)//2):\n",
    "                if (l[i]==f and l[len(l)-1-i]==s) or (l[i]==s and l[len(l)-1-i]==f):\n",
    "                    times.add(t)\n",
    "                    return\n",
    "            for i in range(1<<(len(l)//2)):\n",
    "                # print(i,t)\n",
    "                nl=[]\n",
    "                if len(l)%2==1: nl.append(l[len(l)//2])\n",
    "                # 11111\n",
    "                for _ in range(len(l)//2):\n",
    "                    if l[_]==f or l[len(l)-1-_]==f:\n",
    "                        nl.append(f)\n",
    "                        continue\n",
    "                    if l[_]==s or l[len(l)-1-_]==s:\n",
    "                        nl.append(s)\n",
    "                        continue\n",
    "                    result=(i&(1<<(len(l)//2-1-_)))//(1<<(len(l)//2-1-_))\n",
    "                    if result==1:\n",
    "                        nl.append(l[_])\n",
    "                    else:\n",
    "                        nl.append(l[len(l)-1-_])\n",
    "                nl.sort()\n",
    "                helper(nl, f, s, t+1, nl.index(f), nl.index(s))\n",
    "            return\n",
    "        times=set()\n",
    "        l=range(1,n+1)\n",
    "        helper(l, firstPlayer, secondPlayer, 1, l.index(firstPlayer), l.index(secondPlayer))\n",
    "        return [min(times), max(times)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@lru_cache(None)\n",
    "def dfs(l, r, m):\n",
    "    if l == r:\n",
    "        return [1, 1]\n",
    "    if l > r:\n",
    "        l, r = r, l\n",
    "\n",
    "    a, b = inf, 0\n",
    "    # l 的下一个位置的可能范围为 [1, l] (即, l 前面的全负 到 l 前面的全胜)\n",
    "    for i in range(1, l + 1):\n",
    "        # r 的下一个位置的可能范围为 [l - i + 1, r - i] (即, l 和 r 之间的全负 到 l 和 r 之间的全胜)\n",
    "        for j in range(l - i + 1, r - i + 1):\n",
    "            # 判断 i,j 的位置是否合法\n",
    "            if not (m + 1) // 2 >= i + j >= l + r - m // 2:\n",
    "                continue\n",
    "\n",
    "            x, y = dfs(i, j, (m + 1) // 2)\n",
    "            a = min(a, x + 1)\n",
    "            b = max(b, y + 1)\n",
    "\n",
    "    return [a, b]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:\n",
    "\n",
    "        return dfs(firstPlayer, n - secondPlayer + 1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:\n",
    "\n",
    "        a, b, c = firstPlayer - 1, secondPlayer - firstPlayer - 1, n - secondPlayer\n",
    "        if a == c: return [1,1]\n",
    "        if a > c: a, c = c, a\n",
    "        ans = min(len(bin(n-1))-2, c+1)\n",
    "        has = {}\n",
    "        def dfs(x,y,z):\n",
    "            if (x,y,z) not in has:\n",
    "                if x == z: return 1\n",
    "                if x > z: x, z = z, x\n",
    "                tep = float(\"inf\")\n",
    "                if z >= x + y + 2:\n",
    "                    for i in range(x+1):\n",
    "                        for j in range(y+1):\n",
    "                            tep = min(tep, dfs(i,j,(x+y+z-1)//2-i-j))\n",
    "                else:\n",
    "                    for i in range(x+1):\n",
    "                        for j in range(z-x):\n",
    "                            tep = min(tep, dfs(i,j+(x+y-z+1)//2,z-i-j-1))\n",
    "                has[(x,y,z)] = tep + 1\n",
    "            return has[(x,y,z)]\n",
    "        # print(dfs(a,b,c))\n",
    "        # print(has)\n",
    "        return [dfs(a,b,c), ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:\n",
    "        @cache\n",
    "        def dp(n, f, s):\n",
    "            if f+s == n+1:\n",
    "                return (1, 1)\n",
    "            # F(n, f, s) = F(n, n+1-s, n+1-f)\n",
    "            if f+s > n+1:\n",
    "                # f > s_prime\n",
    "                return dp(n, n+1-s, n+1-f)\n",
    "            \n",
    "            n_half = (n+1) // 2\n",
    "            earliest, latest = float(\"inf\"), float(\"-inf\")\n",
    "            if s <= n_half:\n",
    "                for i in range(0, f):\n",
    "                    for j in range(0, s-f):\n",
    "                        x, y = dp(n_half, i+1, i+j+2)\n",
    "                        earliest = min(earliest, x)\n",
    "                        latest = max(latest, y)\n",
    "            else:\n",
    "                # s is on the right side\n",
    "                # transfer s to s' = n+1-s\n",
    "                # s' is on the right side of f\n",
    "                s_prime = n+1 - s\n",
    "                mid = (n - 2 * s_prime + 1) // 2\n",
    "                for i in range(f):\n",
    "                    for j in range(s_prime - f):\n",
    "                        x, y = dp(n_half, i+1, i+j+2+mid)\n",
    "                        earliest = min(earliest, x)\n",
    "                        latest = max(latest, y)\n",
    "            # print(earliest, latest)\n",
    "            return (earliest+1, latest+1)\n",
    "        if firstPlayer > secondPlayer:\n",
    "            firstPlayer, secondPlayer = secondPlayer, firstPlayer\n",
    "        earliest, latest = dp(n, firstPlayer, secondPlayer)\n",
    "        return [earliest, latest]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:\n",
    "        @lru_cache(None)\n",
    "        def dfs(l, r, n):\n",
    "            if l + r == n - 1:\n",
    "                return 1, 1 \n",
    "            first, second = float('inf'), 0 \n",
    "            if l >= n - l - 1 or l > n - r - 1:\n",
    "                l, r = n - r - 1, n - l - 1 \n",
    "            mid = (n + 1) // 2 \n",
    "            for i in range(l + 1):\n",
    "                for j in range(min(r, n - r - 1) - l):\n",
    "                    if r < mid:\n",
    "                        nxt = dfs(i, i + j + 1, mid)\n",
    "                    else:\n",
    "                        nxt = dfs(i, i + j + 1 + (r - n + r + 1 - 1 + 1) // 2, mid)\n",
    "                    first = min(first, nxt[0])\n",
    "                    second = max(second, nxt[1])\n",
    "            return first + 1, second + 1\n",
    "        return dfs(firstPlayer - 1, secondPlayer - 1, n)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:\n",
    "        @cache\n",
    "        def dp(n: int, f: int, s: int) -> (int, int):\n",
    "            if f + s == n + 1:\n",
    "                return (1, 1)\n",
    "            \n",
    "            # F(n,f,s)=F(n,n+1-s,n+1-f)\n",
    "            if f + s > n + 1:\n",
    "                return dp(n, n + 1 - s, n + 1 - f)\n",
    "            \n",
    "            earliest, latest = float(\"inf\"), float(\"-inf\")\n",
    "            n_half = (n + 1) // 2\n",
    "\n",
    "            if s <= n_half:\n",
    "                # s 在左侧或者中间\n",
    "                for i in range(f):\n",
    "                    for j in range(s - f):\n",
    "                        x, y = dp(n_half, i + 1, i + j + 2)\n",
    "                        earliest = min(earliest, x)\n",
    "                        latest = max(latest, y)\n",
    "            else:\n",
    "                # s 在右侧\n",
    "                # s'\n",
    "                s_prime = n + 1 - s\n",
    "                mid = (n - 2 * s_prime + 1) // 2\n",
    "                for i in range(f):\n",
    "                    for j in range(s_prime - f):\n",
    "                        x, y = dp(n_half, i + 1, i + j + mid + 2)\n",
    "                        earliest = min(earliest, x)\n",
    "                        latest = max(latest, y)\n",
    "            \n",
    "            return (earliest + 1, latest + 1)\n",
    "\n",
    "        # F(n,f,s) = F(n,s,f)\n",
    "        if firstPlayer > secondPlayer:\n",
    "            firstPlayer, secondPlayer = secondPlayer, firstPlayer\n",
    "        \n",
    "        earliest, latest = dp(n, firstPlayer, secondPlayer)\n",
    "        dp.cache_clear()\n",
    "        return [earliest, latest]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:\n",
    "        @cache\n",
    "        def dp(n, f, s):\n",
    "            if f+s == n+1:\n",
    "                return (1, 1)\n",
    "            # F(n, f, s) = F(n, n+1-s, n+1-f)\n",
    "            if f+s > n+1:\n",
    "                # f > s_prime\n",
    "                return dp(n, n+1-s, n+1-f)\n",
    "            \n",
    "            n_half = (n+1) // 2\n",
    "            earliest, latest = float(\"inf\"), float(\"-inf\")\n",
    "            if s <= n_half:\n",
    "                for i in range(0, f):\n",
    "                    for j in range(0, s-f):\n",
    "                        x, y = dp(n_half, i+1, i+j+2)\n",
    "                        earliest = min(earliest, x)\n",
    "                        latest = max(latest, y)\n",
    "            else:\n",
    "                # s is on the right side\n",
    "                # transfer s to s' = n+1-s\n",
    "                # s' is on the right side of f\n",
    "                s_prime = n+1 - s\n",
    "                mid = (n - 2 * s_prime + 1) // 2\n",
    "                for i in range(f):\n",
    "                    for j in range(s_prime - f):\n",
    "                        x, y = dp(n_half, i+1, i+j+2+mid)\n",
    "                        earliest = min(earliest, x)\n",
    "                        latest = max(latest, y)\n",
    "            # print(earliest, latest)\n",
    "            return (earliest+1, latest+1)\n",
    "        if firstPlayer > secondPlayer:\n",
    "            firstPlayer, secondPlayer = secondPlayer, firstPlayer\n",
    "        earliest, latest = dp(n, firstPlayer, secondPlayer)\n",
    "        return [earliest, latest]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAndLatest(self, n: int, first: int, second: int) -> List[int]:\n",
    "        @cache\n",
    "        def dfs(n, x, y):\n",
    "            if x - 1 == n - y:\n",
    "                return (1, 1)\n",
    "            if n + 1 - y < x:\n",
    "                return dfs(n, n + 1 - y, n + 1 - x)\n",
    "            half = (n + 1) >> 1\n",
    "\n",
    "            mn = inf\n",
    "            mx = -inf\n",
    "\n",
    "            if y <= half:\n",
    "                for i in range(x):\n",
    "                    for j in range(y - x):\n",
    "                        res = dfs(half, i + 1, i + j + 2)\n",
    "                        mn = min(mn, res[0])\n",
    "                        mx = max(mx, res[1])\n",
    "\n",
    "                return (mn + 1, mx + 1)\n",
    "\n",
    "            y1 = n + 1 - y\n",
    "\n",
    "            mid = (n - 2 * y1 + 1) // 2\n",
    "            for i in range(x):\n",
    "                for j in range(y1 - x):\n",
    "                    res = dfs(half, i + 1, i + j + mid + 2)\n",
    "                    mn = min(mn, res[0])\n",
    "                    mx = max(mx, res[1])\n",
    "            return mn + 1, mx + 1\n",
    "\n",
    "        left, right = sorted((first, second))\n",
    "        return list(dfs(n, left, right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAndLatest(\n",
    "        self, n: int, firstPlayer: int, secondPlayer: int\n",
    "    ) -> List[int]:\n",
    "        # dp[i][j][k] := (earliest, latest) pair w/ firstPlayer is i-th player from\n",
    "        # Front, secondPlayer is j-th player from end, and there're k people\n",
    "        @functools.lru_cache(None)\n",
    "        def dp(l: int, r: int, k: int) -> List[int]:\n",
    "            if l == r:\n",
    "                return [1, 1]\n",
    "            if l > r:\n",
    "                return dp(r, l, k)\n",
    "\n",
    "            a = math.inf\n",
    "            b = -math.inf\n",
    "\n",
    "            # Enumerate all possible positions\n",
    "            for i in range(1, l + 1):\n",
    "                for j in range(l - i + 1, r - i + 1):\n",
    "                    if not l + r - k // 2 <= i + j <= (k + 1) // 2:\n",
    "                        continue\n",
    "                    x, y = dp(i, j, (k + 1) // 2)\n",
    "                    a = min(a, x + 1)\n",
    "                    b = max(b, y + 1)\n",
    "\n",
    "            return [a, b]\n",
    "\n",
    "        return dp(firstPlayer, n - secondPlayer + 1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:\n",
    "        H=set()\n",
    "        def helper(l, f, s, t, idf, ifs):\n",
    "            if (len(l), idf, ifs) in H:\n",
    "                return\n",
    "            H.add((len(l), idf, ifs))\n",
    "            # print(l,t)\n",
    "            for i in range(len(l)//2):\n",
    "                if (l[i]==f and l[len(l)-1-i]==s) or (l[i]==s and l[len(l)-1-i]==f):\n",
    "                    times.add(t)\n",
    "                    return\n",
    "            for i in range(1<<(len(l)//2)):\n",
    "                # print(i,t)\n",
    "                nl=[]\n",
    "                if len(l)%2==1: nl.append(l[len(l)//2])\n",
    "                # 11111\n",
    "                for _ in range(len(l)//2):\n",
    "                    if l[_]==f or l[len(l)-1-_]==f:\n",
    "                        nl.append(f)\n",
    "                        continue\n",
    "                    if l[_]==s or l[len(l)-1-_]==s:\n",
    "                        nl.append(s)\n",
    "                        continue\n",
    "                    result=(i&(1<<(len(l)//2-1-_)))//(1<<(len(l)//2-1-_))\n",
    "                    if result==1:\n",
    "                        nl.append(l[_])\n",
    "                    else:\n",
    "                        nl.append(l[len(l)-1-_])\n",
    "                nl.sort()\n",
    "                helper(nl, f, s, t+1, nl.index(f), nl.index(s))\n",
    "            return\n",
    "        times=set()\n",
    "        l=range(1,n+1)\n",
    "        helper(l, firstPlayer, secondPlayer, 1, l.index(firstPlayer), l.index(secondPlayer))\n",
    "        return [min(times), max(times)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:\n",
    "        # firstPlayer secondPlayer 都是从1开始计数\n",
    "        @cache\n",
    "        def dp(x, y, num):\n",
    "            # 预处理后全部放在左边\n",
    "            if x == y or x+y-1==num:\n",
    "                return 1,1\n",
    "\n",
    "            min_count = sys.maxsize\n",
    "            max_count = -1\n",
    "            next_num = math.floor((num+1)/2)\n",
    "            if x<= next_num and y<=next_num:\n",
    "                # print(\"if x<=num/2 and y<=num/2:\")\n",
    "                x_left_count = x-1\n",
    "                x_right_y_left_count = y-x-1\n",
    "\n",
    "                for i in range(0, x_left_count+1):\n",
    "                    for j in range(0, x_right_y_left_count+1):\n",
    "                        next_i = i+1\n",
    "                        next_j = i+j+2\n",
    "                        print(next_i, next_j)\n",
    "                        if next_i>=next_num/2 and next_j>=next_num/2:\n",
    "                            next_i = next_num - next_i + 1\n",
    "                            next_j = next_num - next_j + 1\n",
    "                        elif next_i > n/2:\n",
    "                            tmp_next_i = n-next_i+1\n",
    "                            if tmp_next_i < next_j:\n",
    "                                next_i = n-next_i+1\n",
    "                                next_j = n-next_j+1\n",
    "                        elif next_j > n/2:\n",
    "                            tmp_next_j = n-next_j+1\n",
    "                            if tmp_next_j < next_i:\n",
    "                                next_i = n-next_i+1\n",
    "                                next_j = n-next_j+1\n",
    "                            \n",
    "                        dp_min, dp_max = dp(min(next_i,next_j), max(next_i, next_j), next_num)\n",
    "                        max_count = max(max_count, dp_max+1)\n",
    "                        min_count = min(min_count, dp_min+1)\n",
    "            else:\n",
    "                duichen_y = num - y + 1\n",
    "                x_left_count = x-1\n",
    "                x_right_duichen_y_left = duichen_y - x -1\n",
    "                # next_num = math.floor((num+1)/2)\n",
    "                duichen_y_right = next_num - duichen_y\n",
    "                for i in range(0, x_left_count+1):\n",
    "                    for j in range(0, x_right_duichen_y_left+1):\n",
    "                        # print(i,j)\n",
    "                        next_i = i + 1\n",
    "                        next_j = i + duichen_y_right + j + 2\n",
    "                        # print(i,j,next_i, next_j)\n",
    "                        if next_i>=next_num/2 and next_j>=next_num/2:\n",
    "                            next_i = next_num - next_i + 1\n",
    "                            next_j = next_num - next_j + 1\n",
    "                        elif next_i > n/2:\n",
    "                            tmp_next_i = n-next_i+1\n",
    "                            if tmp_next_i < next_j:\n",
    "                                next_i = n-next_i+1\n",
    "                                next_j = n-next_j+1\n",
    "                        elif next_j > n/2:\n",
    "                            tmp_next_j = n-next_j+1\n",
    "                            if tmp_next_j < next_i:\n",
    "                                next_i = n-next_i+1\n",
    "                                next_j = n-next_j+1\n",
    "\n",
    "                        dp_min, dp_max = dp(min(next_i,next_j), max(next_i, next_j), next_num)\n",
    "                        max_count = max(max_count, dp_max+1)\n",
    "                        min_count = min(min_count, dp_min+1)\n",
    "            \n",
    "\n",
    "            # print(f\"x{x}y{y}num{num}max_count{max_count}min_count{min_count}\")\n",
    "            return min_count, max_count\n",
    "        if firstPlayer>=n/2 and secondPlayer>=n/2:\n",
    "            firstPlayer = n-firstPlayer+1\n",
    "            secondPlayer = n-secondPlayer+1\n",
    "        elif firstPlayer > n/2:\n",
    "            tmp_firstPlayer = n-firstPlayer+1\n",
    "            if tmp_firstPlayer < secondPlayer:\n",
    "                firstPlayer = n-firstPlayer+1\n",
    "                secondPlayer = n-secondPlayer+1\n",
    "        elif secondPlayer > n/2:\n",
    "            tmp_secondPlayer = n-secondPlayer+1\n",
    "            if tmp_secondPlayer < firstPlayer:\n",
    "                firstPlayer = n-firstPlayer+1\n",
    "                secondPlayer = n-secondPlayer+1\n",
    "            \n",
    "        return dp(min(firstPlayer, secondPlayer), max(firstPlayer, secondPlayer),n)\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:\n",
    "        if firstPlayer + secondPlayer == n + 1:\n",
    "            return 1, 1\n",
    "        mi, mx = inf, -inf \n",
    "        \n",
    "        def dfs(layer, L):\n",
    "            nonlocal mi \n",
    "            nonlocal mx \n",
    "            if layer == n // 2:\n",
    "                new = sorted(L)\n",
    "                fir, sec = new.index(firstPlayer) + 1, new.index(secondPlayer) + 1\n",
    "                new_mi, new_mx = self.earliestAndLatest((n + 1) // 2, fir, sec)\n",
    "                mi = min(new_mi + 1, mi)\n",
    "                mx = max(new_mx + 1, mx)\n",
    "                return             \n",
    "            if layer + 1 in [firstPlayer, secondPlayer]:\n",
    "                dfs(layer + 1, L + [layer + 1])\n",
    "                return \n",
    "            elif n - layer in [firstPlayer, secondPlayer]:\n",
    "                dfs(layer + 1, L + [n - layer])\n",
    "                return \n",
    "            for choice in [layer + 1, n - layer]:\n",
    "                dfs(layer + 1, L + [choice])\n",
    "        \n",
    "        if n % 2 == 0:\n",
    "            dfs(0, [])\n",
    "        else:\n",
    "            dfs(0, [n // 2 + 1])\n",
    "        return [mi, mx]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAndLatest(self, n: int, f: int, s: int) -> List[int]:\n",
    "\n",
    "        @cache\n",
    "        def dfs(mask):\n",
    "            pk = [p+1 for p in range(n) if (mask>>p)&1]            \n",
    "            last = {mask}\n",
    "            for p in range(len(pk)//2): #分层BFS得到下轮剩下选手的所有可能情况\n",
    "                cur = set()\n",
    "                if (pk[p],pk[-1-p])==(f,s): # 提前撞车就说明这是个确定状态，题目规定f总是小于s，可以这样判断\n",
    "                    return [1,1]\n",
    "                for ms in last:\n",
    "                    if pk[p]!=f and pk[p]!=s: # 注意两个最优秀的选手输给其他人是无效状态不予考虑\n",
    "                        cur.add(ms^(1<<(pk[p]-1)))\n",
    "                    if pk[-1-p]!=f and pk[-1-p]!=s:\n",
    "                        cur.add(ms^(1<<(pk[-1-p]-1)))\n",
    "                last = cur\n",
    "\n",
    "            ansn,ansx = n,-1\n",
    "            for ms in last: # 每个当前轮状态的结果取所有下一轮状态的最优值\n",
    "                mn,mx = dfs(ms)\n",
    "                if ansn>1+mn: ansn = 1+mn\n",
    "                if ansx<1+mx: ansx=1+mx\n",
    "            return ansn,ansx\n",
    "\n",
    "        return dfs((1<<n)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\r\n",
    "from math import log2, ceil\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:\r\n",
    "        firstPlayer -= 1\r\n",
    "        secondPlayer -= 1\r\n",
    "        m = ceil(log2(n))\r\n",
    "        dp: dict[int, list[int]] = dict()\r\n",
    "\r\n",
    "        def dfs(st: int) -> list[int]:\r\n",
    "            if st in dp: return dp[st]\r\n",
    "            dp[st] = [m, 0]\r\n",
    "            # bfs to generate all next status\r\n",
    "            q: deque[tuple[int, int, int]] = deque()\r\n",
    "            q.append((0, n - 1, st))\r\n",
    "            while q:\r\n",
    "                i, j, nxt = q.popleft()\r\n",
    "                while i < j and nxt >> i & 1 == 0:\r\n",
    "                    i += 1\r\n",
    "                while i < j and nxt >> j & 1 == 0:\r\n",
    "                    j -= 1\r\n",
    "                if i >= j:\r\n",
    "                    e, l = dfs(nxt)\r\n",
    "                    dp[st][0] = min(dp[st][0], 1 + e)\r\n",
    "                    dp[st][1] = max(dp[st][1], 1 + l)\r\n",
    "                elif i == firstPlayer and j == secondPlayer:\r\n",
    "                    dp[st][0] = dp[st][1] = 1\r\n",
    "                    return dp[st]\r\n",
    "                elif i == firstPlayer or i == secondPlayer:\r\n",
    "                    q.append((i + 1, j - 1, nxt ^ (1 << j)))\r\n",
    "                elif j == firstPlayer or j == secondPlayer:\r\n",
    "                    q.append((i + 1, j - 1, nxt ^ (1 << i)))\r\n",
    "                else:\r\n",
    "                    q.append((i + 1, j - 1, nxt ^ (1 << i)))\r\n",
    "                    q.append((i + 1, j - 1, nxt ^ (1 << j)))\r\n",
    "\r\n",
    "            return dp[st]\r\n",
    "        \r\n",
    "        return dfs((1 << n) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:\n",
    "        firstPlayer -= 1#从0开始状压，所以最佳运动员下标-1\n",
    "        secondPlayer -= 1\n",
    "        @lru_cache(None)\n",
    "        def dfs(state):\n",
    "            l = 0\n",
    "            r = n - 1\n",
    "            s = {state}#将初始状态位加入集合\n",
    "            res = [float(\"inf\"), float(\"-inf\")]\n",
    "            while l < r:#双指针分别指向左右选手\n",
    "                if state >> l & 1 == 0:#当左侧选手出现\n",
    "                    while state >> r & 1 == 1:#寻找右侧选手\n",
    "                        r -= 1\n",
    "                    if l == r:#如果选手相同，说明轮空\n",
    "                        break\n",
    "                    if l in {firstPlayer, secondPlayer} and r in {firstPlayer, secondPlayer}:#如果都是最佳运动员\n",
    "                        return [1, 1]\n",
    "                    elif l in {firstPlayer, secondPlayer}:#左边是，则只能对右侧状压\n",
    "                        s = {i | 1 << r for i in s}\n",
    "                    elif r in {firstPlayer, secondPlayer}:#右边是，则只能对左侧状压\n",
    "                        s = {i | 1 << l for i in s}\n",
    "                    else:#两侧皆可状压\n",
    "                        s = {i | 1 << r for i in s} | {i | 1 << l for i in s}  \n",
    "                    r -= 1\n",
    "                l += 1\n",
    "            for k in s:#对每种可能的状态继续深搜\n",
    "                tmp = dfs(k)\n",
    "                res[0] = min(res[0], tmp[0] + 1)#更新最小值\n",
    "                res[1] = max(res[1], tmp[1] + 1)#更新最大值\n",
    "            return res\n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int):\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def check(cnt, lst):\n",
    "            nonlocal min_round, max_round\n",
    "            # 中止搜索\n",
    "            m = len(lst)\n",
    "            if len(lst)==1 or firstPlayer not in lst or secondPlayer not in lst:\n",
    "                return\n",
    "            # 判断是否二者相遇\n",
    "            for i in range(m//2):\n",
    "                if lst[i] == firstPlayer and secondPlayer == lst[-i-1]:\n",
    "                    if cnt > max_round:\n",
    "                        max_round = cnt\n",
    "                    if cnt < min_round:\n",
    "                        min_round = cnt\n",
    "                    return\n",
    "\n",
    "            # 枚举所有可能的获胜情况\n",
    "            def dfs(pre, post, i, j):\n",
    "                # 中间多一个轮空的\n",
    "                if i == j:\n",
    "                    check(cnt+1, tuple(pre+[lst[i]]+post))\n",
    "                    return\n",
    "                if i > j:\n",
    "                    check(cnt+1, tuple(pre + post))\n",
    "                    return\n",
    "                # 前面的赢\n",
    "                dfs(pre+[lst[i]], post, i+1, j-1)\n",
    "                # 后面的赢\n",
    "                dfs(pre, [lst[j]] + post, i + 1, j - 1)\n",
    "                return\n",
    "\n",
    "            # 枚举进行下一轮\n",
    "            dfs([], [], 0, m-1)\n",
    "            return\n",
    "\n",
    "        # 初始对战\n",
    "        min_round = n\n",
    "        max_round = 0\n",
    "        check(1, tuple(range(1, n+1)))\n",
    "        return [min_round, max_round]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int):\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def check(cnt, lst):\n",
    "            nonlocal min_round, max_round\n",
    "            \n",
    "            # 中止搜索条件\n",
    "            m = len(lst)\n",
    "            if len(lst) == 1 or firstPlayer not in lst or secondPlayer not in lst:\n",
    "                return\n",
    "            \n",
    "            # 判断两位最佳运动员是否相遇\n",
    "            for i in range(m // 2):\n",
    "                if lst[i] == firstPlayer and secondPlayer == lst[-i-1]:\n",
    "                    if cnt > max_round:\n",
    "                        max_round = cnt\n",
    "                    if cnt < min_round:\n",
    "                        min_round = cnt\n",
    "                    return\n",
    "\n",
    "            # 枚举所有可能的获胜情况\n",
    "            def dfs(pre, post, i, j):\n",
    "                if i == j:\n",
    "                    check(cnt + 1, tuple(pre + [lst[i]] + post))\n",
    "                    return\n",
    "                if i > j:\n",
    "                    check(cnt + 1, tuple(pre + post))\n",
    "                    return\n",
    "                # 前面的赢\n",
    "                dfs(pre + [lst[i]], post, i + 1, j - 1)\n",
    "                # 后面的赢\n",
    "                dfs(pre, [lst[j]] + post, i + 1, j - 1)\n",
    "                return\n",
    "\n",
    "            dfs([], [], 0, m - 1)\n",
    "            return\n",
    "\n",
    "        # 初始对战\n",
    "        min_round = n\n",
    "        max_round = 0\n",
    "        check(1, tuple(range(1, n + 1)))\n",
    "        return [min_round, max_round]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
